package com.leetcode.partition8;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2021/10/12 10:44
 */
public class LC787K站中转内最便宜的航班 {

    private static final int INF = Integer.MAX_VALUE >> 1;

    public static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        return bellmanFord(n, flights, src, dst, k);
    }

    public static void main(String[] args) {
//        int[][] flights = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
//        System.out.println(findCheapestPrice(3, flights, 0, 2, 1));
        int[][] flights = {{0, 1, 100}, {0, 4, 500}, {1, 2, 200}, {1, 3, 100}, {3, 4, 100}, {0, 5, 100}, {5, 4, 250}, {2, 6, 100}};
        System.out.println(findCheapestPrice(7, flights, 0, 6, 2));
//        int[][] flights = {{0, 1, 1}, {0, 2, 5}, {1, 2, 1}, {2, 3, 1}};
//        System.out.println(findCheapestPrice(4, flights, 0, 3, 1));
    }

    private static int bellmanFord(int n, int[][] flights, int src, int dst, int k) {
        int[] costs = new int[n];
        Arrays.fill(costs, INF);
        costs[src] = 0;
        for (int i = 1; i <= k + 1; i++) {
            //复制松弛前状态的costs，避免在松弛的过程中动态的更新
            int[] copyCosts = Arrays.copyOf(costs, n);
            for (int[] flight : flights) {
                costs[flight[1]] = Math.min(costs[flight[1]], copyCosts[flight[0]] + flight[2]);
            }
        }
        return costs[dst] == INF ? -1 : costs[dst];
    }

    private static int dijkstra(int n, int[][] flights, int src, int dst, int k) {
        int[][] matrix = new int[n][n];
        //将边转换为邻接矩阵
        for (int[] flight : flights) matrix[flight[0]][flight[1]] = flight[2];
        //使用小顶堆优化迪杰斯特拉算法        {(vertex, cost, steps), ...}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));
        int[] costs = new int[n];
        int[] steps = new int[n];
        Arrays.fill(costs, Integer.MAX_VALUE);
        costs[src] = 0;
        minHeap.offer(new int[]{src, 0, k});
        while (!minHeap.isEmpty()) {
            int[] nearestNeighbor = minHeap.poll();
            int nearestIndex = nearestNeighbor[0], nearestCost = nearestNeighbor[1], nearestStep = nearestNeighbor[2];
            //已经到达了目的地
            if (nearestNeighbor[0] == dst) return nearestCost;
            //当前节点已经没有剩余可用的步数，因此不进行移动，continue到下一个节点
            if (nearestStep < 0) continue;
            for (int i = 0; i < matrix[0].length; i++) {
                if (matrix[nearestIndex][i] <= 0) continue;
                int cost = nearestCost + matrix[nearestIndex][i];
                if (cost < costs[i]) {
                    //已经移动了一步，装入的step需要减1
                    minHeap.offer(new int[]{i, matrix[nearestIndex][i] + nearestCost, nearestStep - 1});
                    costs[i] = cost;
                    steps[i] = nearestStep - 1;
                } else if (steps[i] < nearestStep - 1) {
                    minHeap.offer(new int[]{i, cost, nearestStep - 1});
                }
            }
        }
        return -1;
    }
}
